#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2022/1/10 10:54
# @Software: PyCharm
# @File    : l523_check_sum_array_sum.py
from typing import List


class Solution:
    def checkSubarraySum_1(self, nums: List[int], k: int) -> bool:
        '''
        暴力法，双循环
        :param nums:
        :param k:
        :return:
        '''
        sums = {}
        sum_c = 0
        for (idx, v) in enumerate(nums):
            sum_c += v
            sums[idx] = sum_c
            if idx > 0:
                if sum_c % k == 0:
                    return True
                else:
                    for i in range(idx - 1):
                        tmp = sum_c - sums[i]
                        if tmp % k == 0:
                            # print(sum_c, sums[i], i, idx, sums)
                            return True
        return False

    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        '''
        前缀和
        余数和
        一次遍历（两次同样的余数出现，表示2次中间的数和可以整除k，只需判断2次中间的数的个数>=2即可）
        :param nums:
        :param k:
        :return:
        '''
        sums = {0: -1}
        remainder = 0
        for (idx, v) in enumerate(nums):
            remainder = (remainder + v) % k
            if remainder in sums:
                prev_idx = sums.get(remainder)
                if idx - prev_idx > 1:
                    print(sums)
                    return True
            else:
                sums[remainder] = idx
        return False


if __name__ == '__main__':
    s = Solution()
    nums = [23, 2, 4, 6, 6]
    k = 7
    # nums = [5, 0, 0, 0]
    # k = 3
    print(s.checkSubarraySum(nums, k))
